package com.yww.leetcode.linkedlist;

import com.yww.leetcode.common.ListNode;

/**
 * @author yww
 * @description 203. 移除链表元素
 * @since 2024/2/2 11:42
 */
public class RemoveElements203 {
    // 给你一个链表的头节点 head 和一个整数 val ，
    // 请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
    public ListNode removeElements(ListNode head, int val) {
        if (val % 2 == 0) {
            return remove01(head, val);
        }
        return remove02(head, val);
    }

    // 方法1：循环双指针
    private ListNode remove01(ListNode head, int val) {
        // 创建哨兵，对空链表方便处理
        ListNode sentinel = new ListNode(-1, head);
        // 前驱，删除节点的前驱
        ListNode p1 = sentinel;
        // 作为遍历节点
        ListNode p2 = p1.next;
        while (p2 != null) {
            // 是要删除的节点
            if (p2.val == val) {
                // 删除p2节点，跳过p2节点
                p1.next = p2.next;
                // p2后移
                p2 = p2.next;
            } else {
                // p1后移
                p1 = p1.next;
                // p2后移
                p2 = p2.next;
            }
        }
        return sentinel.next;
    }

    // 方法2：递归
    private ListNode remove02(ListNode cur, int val) {
        if (cur == null) { // 结束条件
            return null;
        }
        if (cur.val == val) {
            // 如果当节点的值是要删除的值，就跳过当前节点，返回下一个节点的递归处理结果
            return remove02(cur.next, val);
        } else {
            // 如果当节点不是要删除的，就返回当前节点，下一个节点继续递归处理
            cur.next = remove02(cur.next, val);
            return cur;
        }
    }


}
